package com.df.tree;


import com.df.storage.Node;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树
 *
 * 建树
 * 深度遍历：前序，中序，后续
 * 广度遍历
 *
 * @author dongfang
 */
public class BinaryTree {


    public static void main(String[] args) {

        int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

        LinkedList<Node> mLinkedList = create(array);

        preorder_btree(mLinkedList.getFirst());
        preorderBtree(mLinkedList.getFirst());
//        inorder_btree(mLinkedList.getFirst());
//        postorder_btree(mLinkedList.getFirst());

//        breadth_first(mLinkedList.getFirst());


    }

    /**
     * 建二叉搜索树
     *
     * @param array 原始数据源
     * @return 建好树的二叉树
     */
    static LinkedList<Node> create(int[] array) {
        LinkedList<Node> mLinkedList = null;
        if (array != null && array.length > 0) {
            mLinkedList = new LinkedList<>();
            Node node = new Node(array[0]);
            mLinkedList.add(node);
            for (int i = 0, length = array.length; i < (length >> 1); i++) {

                if (((i << 1) + 1) < length) {
                    Node l = new Node(array[(i << 1) + 1]);
                    mLinkedList.get(i).left = l;
                    mLinkedList.add(l);
                }
                if (((i << 1) + 2) < length) {
                    Node r = new Node(array[(i << 1) + 2]);
                    mLinkedList.get(i).right = r;
                    mLinkedList.add(r);
                }
            }
        }

        return mLinkedList;
    }

    /**
     * 前序遍历
     *
     * @param node 开始结点
     */
    static void preorder_btree(Node node) {
        if (null != node) {
            System.out.println("preorder " + node.value);
            preorder_btree(node.left);
            preorder_btree(node.right);

        }
    }

    /**
     * 非递归线序
     *
     * @param node 开始结点
     */

    static void preorderBtree(Node node) {
        if (null == node) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node n = stack.pop();
            System.out.println("preorderBtree " + n.value);


            if (null != n.right) {
                stack.push(n.right);
            }

            if (null != n.left) {
                stack.push(n.left);
            }
        }
    }


    /**
     * 中序遍历
     *
     * @param node 开始结点
     */
    static void inorder_btree(Node node) {
        if (null != node) {
            inorder_btree(node.left);
            System.out.println("inorder " + node.value);
            inorder_btree(node.right);
        }
    }

    /**
     * 后序遍历
     *
     * @param node 开始结点
     */
    static void postorder_btree(Node node) {
        if (null != node) {
            postorder_btree(node.left);
            postorder_btree(node.right);
            System.out.println("postorder " + node.value);
        }
    }

    /**
     * 广度优先遍历
     *
     * 主要是用队列，在遍历结点的时候，把该结点的子结点都放到队列中（在最后），然后循环获取队列头的数据；
     *
     * @param node
     */
    static void breadth_first(Node node) {
        if (null == node) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();

        queue.add(node);
        while (!queue.isEmpty()) {
            Node n = queue.poll();
            System.out.println("breadth_first " + n.value);
            if (null != n.left) {
                queue.add(n.left);
            }
            if (null != n.right) {
                queue.add(n.right);
            }
        }
    }

}
